|
Graph pebbling is a mathematical game and area of interest played on a graph with pebbles on the vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of taking two pebbles off one vertex and placing one on an adjacent vertex (the second removed pebble is discarded from play). π(''G''), the pebbling number of a graph ''G'' is the lowest natural number ''n'' that satisfies the following condition:
For example, on a graph with 2 vertices and 1 edge connecting them the pebbling number is 2. No matter how the two pebbles are placed on the vertices of the graph it is always possible to move a pebble to any vertex in the graph. One of the central questions of graph pebbling is the value of π(''G'') for a given graph ''G''. Other topics in pebbling include cover pebbling, optimal pebbling, domination cover pebbling, bounds, and thresholds for pebbling numbers, deep graphs, and others. ==π(''G'') — the pebbling number of a graph== The game of pebbling was first suggested by Lagarias and Saks, as a tool for solving a particular problem in number theory. In 1989 F.R.K. Chung introduced the concept in the literature and defined the pebbling number, π(''G''). The pebbling number for a complete graph on ''n'' vertices is easily verified to be ''n'': If we had (''n'' − 1) pebbles to put on the graph, then we could put 1 pebble on each vertex except one. This would make it impossible to place a pebble on the last vertex. Since this last vertex could have been the designated target vertex, the pebbling number must be greater than ''n'' − 1. If we were to add 1 more pebble to the graph there are 2 possible cases. First, we could add it to the empty vertex, which would put a pebble on every vertex. Or secondly, we could add it to one of the vertices with only 1 pebble on them. Once any vertex has 2 pebbles on it, it becomes possible to make a pebbling move to any other vertex in the complete graph. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Graph pebbling」の詳細全文を読む スポンサード リンク
|